package backTrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N 皇后
 */
public class P51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> totalList = new ArrayList<>();
        backTrack(n, n, new ArrayList<Integer>(), totalList);
        return totalList;
    }

    private void backTrack(int n, int len, List<Integer> subList, List<List<String>> totalList) {
        if (len == 0) {// 到达指定长度
            List<String> list = new ArrayList<>();
            subList.stream().forEach(idx -> {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++)
                    sb.append(".");
                sb.setCharAt(idx, 'Q');
                list.add(sb.toString());
            });
            totalList.add(list);
        } else {
            for (int i = 0; i < n; i++) {
                if (checkValid(n, subList, i)) {
                    subList.add(i);
                    backTrack(n, len - 1, subList, totalList);
                    subList.remove(subList.size() - 1);
                }
            }
        }
    }

    private boolean checkValid(int n, List<Integer> subList, int col) {
        // 检查列
        for (int num : subList) {
            if (num == col)
                return false;
        }
        // 检查正对角线
        int tmp = col;
        for (int i = subList.size() - 1; i >= 0 && tmp < n; i--) {
            if (subList.get(i) == ++tmp) {
                return false;
            }
        }
        // 检查负对角线
        tmp = col;
        for (int i = subList.size() - 1; i >= 0 && tmp >= 0; i--) {
            if (subList.get(i) == --tmp) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<List<String>> lists = new P51().solveNQueens(4);
        for (List<String> list : lists) {
            System.out.println();
            for (String item : list) {
                System.out.println(item);
            }
            System.out.println();
        }
    }
}
